package acwing.数学.快速幂;

import java.util.Scanner;

/**
 * 快速幂
 *
 * @author yang
 * @date 2022/1/16
 */
public class 快速幂 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long p = sc.nextLong();
            System.out.println(qmi(a,b,p));
        }
    }

    private static long qmi(long a, long b, long p) {
        long res = 1;
        while (b != 0) {
            if ((b & 1) == 1) res = res * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return res;
    }
}
